0990. 等式方程的可满足性【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 并查集

1. 📝 题目描述

• leetcode

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。

---

示例 1：

输入：["a==b","b!=a"]
输出：false

解释：
如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。
没有办法分配变量同时满足这两个方程。

---

示例 2：

输入：["b==a","a==b"]
输出：true

解释：
我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。

---

示例 3：

输入：["a==b","b==c","a==c"]
输出：true

---

示例 4：

输入：["a==b","b!=c","c==a"]
输出：false

---

示例 5：

输入：["c==c","b==d","x!=z"]
输出：true

---

提示：

1. 1 <= equations.length <= 500
2. equations[i].length == 4
3. equations[i][0] 和 equations[i][3] 是小写字母
4. equations[i][1] 要么是 '='，要么是 '!'
5. equations[i][2] 是 '='

2. 🎯 s.1 - 并查集

js

/**
 * @param {string[]} equations
 * @return {boolean}
 */
var equationsPossible = function (equations) {
  // 并查集：26 个小写字母
  const parent = Array.from({ length: 26 }, (_, i) => i)

  // 查找根节点（带路径压缩）
  const find = (x) => {
    if (parent[x] !== x) {
      parent[x] = find(parent[x])
    }
    return parent[x]
  }

  // 合并两个集合
  const union = (x, y) => {
    parent[find(x)] = find(y)
  }

  // 第一步：处理所有相等关系，合并到同一集合
  for (const eq of equations) {
    if (eq[1] === '=') {
      const x = eq.charCodeAt(0) - 97 // 'a' 的 ASCII 码为 97
      const y = eq.charCodeAt(3) - 97
      union(x, y)
    }
  }

  // 第二步：检查所有不等关系
  for (const eq of equations) {
    if (eq[1] === '!') {
      const x = eq.charCodeAt(0) - 97
      const y = eq.charCodeAt(3) - 97
      // 如果两个变量在同一集合中，但要求不等，矛盾
      if (find(x) === find(y)) {
        return false
      }
    }
  }

  return true
}

• 时间复杂度：$O(n\times \alpha (26))$，其中 n 是方程数量，$\alpha$ 是阿克曼函数的反函数，可视为常数
• 空间复杂度：$O(26)=O(1)$，并查集数组的空间

算法思路：

• 并查集初始化：为 26 个小写字母创建并查集，初始时每个字母是独立的集合
• 第一阶段：遍历所有相等方程（==），将相等的变量合并到同一个集合中
• 第二阶段：遍历所有不等方程（!=），检查不等的两个变量是否在同一集合中
• 矛盾检测：如果不等方程中的两个变量在同一集合，说明它们应该相等，产生矛盾，返回 false
• 路径压缩：在查找根节点时使用路径压缩优化，将节点直接连接到根节点，提高后续查找效率